package main

type Node struct {
	start int
	end   int
	val   int
	left  *Node
	right *Node
}

type NumArray struct {
	root *Node
}

func Constructor(nums []int) NumArray {
	root := &Node{}
	build(nums, root, 0, len(nums)-1)
	return NumArray{
		root: root,
	}
}

func build(nums []int, node *Node, start int, end int) {
	node.start = start
	node.end = end
	if start == end {
		node.val = nums[start]
		return
	}
	node.left = &Node{}
	node.right = &Node{}
	mid := (start + end) / 2
	build(nums, node.left, start, mid)
	build(nums, node.right, mid+1, end)
	node.val = node.left.val + node.right.val
}

func (this *NumArray) Update(index int, val int) {
	Update(this.root, index, val)
}

func Update(node *Node, index int, val int) {
	if index == node.start && index == node.end {
		node.val = val
		return
	}
	if node.left != nil && index <= node.left.end {
		Update(node.left, index, val)
	}
	if node.right != nil && index >= node.right.start {
		Update(node.right, index, val)
	}
	node.val = node.left.val + node.right.val
}

func (this *NumArray) SumRange(left int, right int) int {
	return SumRange(this.root, left, right)
}


func SumRange(node *Node, left int, right int) int {
	if left <= node.start && right >= node.end {
		return node.val
	}
	ans := 0
	if node.left != nil && left <= node.left.end {
		ans += SumRange(node.left, left, right)
	}
	if node.right != nil && right >= node.right.start {
		ans += SumRange(node.right, left, right)
	}
	return ans
}

func main() {
	arr := Constructor([]int{0,9,5,7,3})
	println(arr.SumRange(4, 4))
	arr.Update(1, 2)
	println(arr.SumRange(0, 2))
}